package com.conjane.algo.linked_list;

public class HasCycle {

    private static boolean check(ListNode<Integer> listNode){
        // 记录每次访问的记录节点
        ListNode[] array = new ListNode[10000];
        ListNode headNode = listNode;
        while (headNode != null){
            for (int i = 0; i < array.length; i++) {
                // 如果当前节点，跟遍历中的节点相同，则发现环形，返回true
                if (array[i] == headNode){
                    return true;
                }
                // 如果数组当前节点为空，则放入当前节点数据
                if (array[i] == null){
                    array[i] = headNode;
                    break;
                }
            }
            headNode = headNode.next;
        }
        return false;
    }

    /**
     * 利用快慢指针
     * @param listNode
     * @return
     */
    private static boolean checkPlus(ListNode<Integer> listNode){
        ListNode slow = listNode;
        ListNode fast = listNode.next;
        while (slow != null && fast != null){
            if (slow == fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode<Integer> a = new ListNode<>(1);
        ListNode<Integer> b = new ListNode<>(2);
        ListNode<Integer> c = new ListNode<>(3);
        ListNode<Integer> d = new ListNode<>(2);
        a.next = b;
        b.next = c;
        c.next = a;
        System.out.println(checkPlus(a));
    }
}
